1. Field of the Invention
The present invention relates generally to data management, and more particularly to the management of data in a computer system by a data storage system.
2. Description of the Prior Art
Host processor systems may store and retrieve data using one or more data storage systems containing a plurality of host interface units (host adapters), disk data storage devices, and disk interface units (disk adapters), as well as a cache memory. Such data storage systems are provided, for example, by EMC Corporation of Hopkinton, Mass. and disclosed in U.S. Pat. Nos. 5,206,939 to Yanai et al., 5,778,394 to Galtzur et al., U.S. Pat. No. 5,845,147 to Vishlitzky et al., and U.S. Pat. No. 5,857,208 to Ofek. The host systems access the data storage systems through a plurality of channels provided therewith. Host systems provide data and access control information through the channels of the data storage systems and the data storage systems provides data to the host systems also through the channels. The host systems do not address the disk data storage devices of the data storage system directly, but rather, access what appears to the host systems as a plurality of logical volumes. These logical locations are mapped into physical locations on the disk data storage devices, but the logical volumes may be larger or smaller than the corresponding disk data storage devices, and may span multiple drives. A single logical location may also be mapped to multiple physical locations, when, for example, data mirroring is desired.
Cache memory may be used to store frequently accessed data for rapid access. Typically, it is time-consuming to read or compute data stored in the disk data storage devices. However, once data is stored in the cache memory, future use can be made by accessing the cached copy rather than reading it from the disk data storage device, so that average access time to data may be made lower.
One technique for expediting read requests involves prefetching data units so that more data units will available from cache memory rather than from disk storage. Typically, prefetching is implemented by reading data units in blocks in response to one or more requests to read a data unit. Since a request to read a specific data unit increases the likelihood that access to other, related data units will soon be required, the read request for the data unit may trigger a prefetch request to read related data units as well, particularly when a read request results in reading a data unit off-cache rather than from the cache memory.
Rules may be developed to govern the triggering of a prefetch operation. For example, a prefetch operation may be executed upon issuance of a single request to read a data unit off-cache. Alternatively, a prefetch operation may not be triggered by a selected number of read requests for an off-cache data unit.
When, in the course of executing a read request, the requested data unit is found in-cache, the operation constitutes a “Hit.” If the requested data unit is not found in-cache, the operation constitutes a “Miss.”
Sequential prefetching, which involves reading blocks of adjacent data units, assumes that data units that are adjacent to a requested data unit are also likely to be accessed. In fact, access requests often involve data units that are sequential. Recognizing that the physical devices, such as disks, upon which data is stored off-cache, are organized and segmented into one or more logical volumes (LVs), the addresses of the adjacent data units may not be physically sequential on the disk, but they will be sequential on the logical volume to which the data on the disk is mapped.
As an example, consider a series of six adjacent data units, namely (a, b, c, d, e, f). If requests to read the data units a, b and then c are issued by a host processor for use in an I/O operation, a sequential access of data units (a, b, c) may be recognized, leading to the assumption that data units d, e and f will also be needed. In response, a prefetch task for prefetching the sequential stream of data units may be opened. A first prefetch operation is initiated under the prefetch task to prefetch data units d and e. When the first prefetch operation is completed, a second prefetch operation is initiated under the prefetch task to prefetch data units f and g. More than one prefetch task may be opened at the same time, executing prefetch operations for different sequential streams of data units.
Prefetching requires a significant number of cache-slots to be available in the cache memory. When long sequences of data units are prefetched into the cache memory, other data units typically have to be removed in the cache memory in order to make room for the newly prefetched data units.
One problem with prefetching is that the data units that are prefetched are not necessarily going to be accessed, for example by a host processor. A possibility arises that the host processor will access them because they are adjacent to a data unit that it had required, but it is not a certainty that the host processor will require the prefetched data units. Prefetching involves retrieving data units that the host may or may not need. On the other hand, prefetching involves removing in-cache data units that still have some probability of being accessed. Therefore, prefetching raises the possibility that data units for which the host processor requires access may be replaced by data units for which the host processor does not and never will require access. It is therefore, important to remove cache data that is not likely to be still required by the data storage system. Cache Pollution is defined to be the population of the cache memory with data units that are not required for re-accessing, for example, by a host processor.
One data caching process for determining which data units in a cache memory to overwrite is the Least Recently Used (LRU) process, which discards the least recently used data units first, operating under the assumption that the data unit that was the earliest accessed (for example, by a host processor), is the data unit that is likeliest not to be required by a host processor again. Therefore, in the LRU process, the data unit to remove in a cache memory is the least recently used data unit. The cache-slot that holds the least recently used data unit may be known as the “LRU cache-slot”.
Other data caching processes decide which data units to remove based on the Tagged Based Cache (TBC) or the LRU time stamp (LRUTS) rather than the LRU data unit. Despite the data caching process used, it is necessary to keep track of which data units were accessed or used and when, which may be expensive in time and resources.
In a long sequential stream, the data units that had been prefetched into the cache memory and accessed by the host processor are not likely to be re-accessed by the host processor, and thus constitute cache pollution.
A feature known as “tail cutting” or simply “cutting” may be used to reduce this form of cache pollution. In tail cutting, a maximum number of data units may be stored in the cache memory pursuant to a prefetch task. Once the maximum number has been prefetched into cache memory, certain data units will be removed from the cache memory to make room for data units prefetched pursuant to the prefetch task or pursuant to another prefetch task.
For example, if thirty five is chosen as the maximum number of data units to be stored in cache memory pursuant to a first prefetch task, after thirty five data units are prefetched and stored in the cache memory, if one more data unit is prefetched to store in cache memory, a data unit earlier prefetched pursuant to the first prefetch task and already read by the host will be removed from cache memory to make room for the newly prefetched data unit.
A data storage system featuring sequential prefetching operations with tail cutting is disclosed in U.S. Pat. No. 5,537,568, entitled System For Dynamically Controlling Cache Manager Maintaining Cache Index And Controlling Sequential Data Access, Yanai, et al., which is hereby incorporated by reference.
Tail cutting can limit cache pollution due to sequential prefetching so long as the prefetch operation executes quickly enough that data units are prefetched and stored in the cache memory faster than they are required in a read request. Returning to the example provided above, when a prefetch operation is issued in response to a request to read a data unit d, it should be noted that the next read request is likely to be for a data unit e that is adjacent to the data unit d. The adjacent data unit e will be in the block of data units being prefetched pursuant to the first prefetch operation.
When the prefetch operation executes faster than a host processor can request a read of its next data unit, storage of the adjacent data unit e in the cache memory will have been completed before issuance of the next read command. A read request for the data unit e will result in a Hit (data unit e being found in-cache), and the data unit e will be read from its cache-slot. However, when the prefetch operation executes more slowly than the host processor can request a read of its next data unit through the host adapter, the adjacent data unit e may not yet be stored in the cache memory and the read request will result in a Miss (data unit e not being found in-cache). The data unit e will be read from its location off-cache.
As noted before, a read request for data units that are out-of-cache will take longer to execute than a request for data units that are in-cache. Therefore, it is not preferable to retrieve the data unit e from its location off-cache if it can be read from an in-cache location. In addition, procedurally, a disk adapter will execute a read request before it completes a prefetch operation. Therefore, the disk adapter will execute the read request for the data unit e before it completes the prefetch operation in which the data unit e would have been retrieved.
Finally, a Miss operation may result in not updating the count of the number of prefetched data units in the sequence being prefetched pursuant to the prefetch task. The prefetched data unit count was being made in anticipation of making a tail cut on the original prefetch operation. This will impact future prefetches and future tail cuts.
The problem is further exacerbated when a host adapter then issues a read request for the data unit f, which is adjacent to data unit e, and which would have been prefetched pursuant to the second prefetch operation, which had not been initiated yet. The second prefetch operation would not have had an opportunity to prefetch data unit f into the cache memory. Therefore, the read request for data unit f will result in a Miss operation and will proceed to read data unit f from its off-cache logical location. As previously indicated, the physical devices which store data off-cache are organized and segmented into logical volumes, and in sending a read request off-cache, the logical address requested will be mapped to the corresponding physical location. Off-cache logical location means the physical location in the data storage devices, e.g. disk data storage devices, of this part (IN THIS CASE, DATA UNIT F) of the logical volume. Once again, the prefetch operation is disrupted and the prefetched data unit count is not updated.
Three kinds of Miss operations may be defined. A Short Miss (SM) operation occurs when prefetching of a data unit had started but not been completed before the issuance of a read request for the data unit. The new input/output (I/O) request was received from the host processor to read a data unit that is currently in the middle of prefetch operation. A Long Miss (LM) operation occurs when the command to start a prefetch operation had issued, but had not been sent to the disk before the issuance of a read request for a data unit. The new I/O instruction was received from the host processor to read a data unit that was going to be prefetched next. A Read Miss operation occurs when a new I/O request is issued for a data unit for which no plans to prefetch were yet made. In all three cases the data is not in-cache when a read request issues.
Using the example of the prefetches above, in which a sequential access is detected upon reading of data units a, b, c, and a first prefetch task is opened to prefetch the new sequential stream started by data units a, b, c, the first prefetch task issues a first prefetch operation for prefetching data units d, e, followed by a second prefetch operation for prefetching data units f, g. It can be seen in the example that sequential prefetching tasks are opened after three Miss operations.
Consider the situation in which the timing of prefetch operations relative to the timing of read requests is such that, after prefetching five data units, the data units required for reading by the host processor will not have yet been prefetched into the cache memory. Returning to the example, when a prefetch task opens in response to a read request for data unit c, the data storage system is able to complete the prefetching of data units d, e, f, g, h, but will not have stored data unit i before a read request for data unit i is issued. Read requests for data units i, j, and k result in Miss operations and in a recognition of a new sequence (i, j, k, . . . ). In response thereto, a new prefetch task may be opened to fill the cache memory with the new sequence (i, j, k . . . ).
The data units i, j, k are not identified as related to the prefetch task with which the data units d, e, f were prefetched. Therefore, they will not be used as part of a prefetched data unit count to determine when tail cutting is appropriate for the prefetch task in which data units d, e, f were prefetched. In addition, the data units i, j, k will remain in storage in cache memory longer than had they been identified as related to the prefetch task with which the data units d, e, f were prefetched. Because they are not recognized as stored pursuant to the prefetch task, they will not be recycled (i.e., removed from the cache memory) pursuant to the tail cut of the prefetch task. For recycling purposes, they will be treated as general data units stored in cache memory, therefore remaining in cache memory longer than they would have remained had they been identified as related to the prefetch task with which the data units d, e, f were prefetched. Further, the data units d, e, f in the prefetch task will also remain in cache memory longer than they would have had the data units i, j, k been recognized as part of the prefetch task. Even though the sequential activity continues, there are no new data units retrieved pursuant to the prefetch task to which the data units d, e, f are associated. Therefore, the data units d, e, f will not be recycled. Such prefetch tasks are known as orphan prefetches, and sequences of data units associated with them are known as orphan prefetch sequences.
A second prefetch sequence may be recognized, and a second prefetch task may be opened in response. The second prefetch task issues prefetch operations to prefetch data units into the cache memory. As a new sequence, starting with data unit i, begins to be prefetched into the cache memory, the data unit i constitutes the start of a new sequence count. Recalling that the data system is not capable of prefetching faster than the issuance of a sixth read request, the data units (i, j, k, l, m) are prefetched, but read requests for data units n, o, p also result in Miss operations. The data units n, o, p will not be identified as related to the second prefetch task with which the data units i, j, k were prefetched. Therefore, they will not be used as part of the prefetched data unit count to determine when tail cutting is appropriate for the second prefetch task in which data units i, j, k were prefetched. In addition, the data units n, o, p will be treated as general data units and remain in storage in cache memory longer than had they been identified as related to the prefetch task with which the data units i, j, k were prefetched. Further, the second prefetch task also constitutes an orphan prefetch, and the data units i, j, k associated with it constitute another orphan prefetch sequence that will not be recycled. The second prefetch task may also be terminated before completion and a third prefetch task may be opened to fill the cache memory.
Starting and stopping prefetch operations and tasks have administrative overhead associated with them. Therefore, it is not preferable to stop a prefetch operation or task and start others for the same series of data units. It can be seen then that prefetching with a tail cut, as it is conventionally implemented in data storage system, will only execute to completion when a data storage system is able to prefetch and store data units in the cache memory faster than the data units are required for read requests. It would be advantageous to provide a prefetch implementation in which the data storage system prefetches and stores data units in the cache memory and make decisions on the execution of prefetch operations and data unit storage, including tail cutting, even when read requests issue for data units before a prefetch operation is completed or even issued.